package Queue_and_Stack;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class _34逆波兰表达式求值 {
    public static void main(String[] args) {
        String[] s = {"2","1","+","3","*"};
        System.out.println(evalRPN(s));
    }

    //栈
    //O(n)  O(n)
    public static int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        Integer p1;
        Integer p2;
        for (String token : tokens) {
            switch (token) {
                case "+":
                    p1 = stack.pop();
                    p2 = stack.pop();
                    stack.push(p2 + p1);
                    break;
                case "-":
                    p1 = stack.pop();
                    p2 = stack.pop();
                    stack.push(p2 - p1);
                    break;
                case "*":
                    p1 = stack.pop();
                    p2 = stack.pop();
                    stack.push(p2 * p1);
                    break;
                case "/":
                    p1 = stack.pop();
                    p2 = stack.pop();
                    stack.push(p2 / p1);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    //官解二：数组模拟栈
    //O(n)  O(n)    数据小的时候空间更小
    class Solution {
        public int evalRPN(String[] tokens) {
            int n = tokens.length;
            int[] stack = new int[(n + 1) / 2];
            int index = -1;
            for (int i = 0; i < n; i++) {
                String token = tokens[i];
                switch (token) {
                    case "+":
                        index--;
                        stack[index] += stack[index + 1];
                        break;
                    case "-":
                        index--;
                        stack[index] -= stack[index + 1];
                        break;
                    case "*":
                        index--;
                        stack[index] *= stack[index + 1];
                        break;
                    case "/":
                        index--;
                        stack[index] /= stack[index + 1];
                        break;
                    default:
                        index++;
                        stack[index] = Integer.parseInt(token);
                }
            }
            return stack[index];
        }
    }

}
